package com.lisp.algorithm.book.c15.q4_5;

import java.util.Arrays;

public class Q4_5 {

	public static void main(String[] args) {
		int a[] = {5, 4, 3, 2, 1};
		System.out.println(longestMonotonicallyIncreasingSequence(a));
	}
	
	private static int longestMonotonicallyIncreasingSequence(int a[]) {
		int solution[] = new int[a.length];
		solution[0] = 1;
		int maxLength = 1;
		for(int i=1; i<a.length; i++) {
			int maxLengthEndWithAI = 1;
			for(int j=i-1; j>=0; j--) {
				if(a[i] >= a[j] && solution[j] + 1 > maxLengthEndWithAI) {
					maxLengthEndWithAI = solution[j] + 1;
				}
			}
			solution[i] = maxLengthEndWithAI;
			if(maxLength < maxLengthEndWithAI) {
				maxLength = maxLengthEndWithAI;
			}
		}
		System.out.println(Arrays.toString(solution));
		return maxLength;
	}
}
